package offerbook;


import utils.TreeNode;
import utils.TreeUtil;

import java.util.Arrays;

/**
 * {@link Code24_VerifySequenceOfBST}
 * @date 2020/3/7 22:50
 */
public class Code06_ReConstructBT_二叉树重建 {
    public static TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        //pre的第0号元素为root，找到root所在的in位置设置为inIndex，
        // in左侧在root左子树，in右侧在root右子树
        //root.left = pre[1],root[right] = pre[inIndex+1]
        if(pre == null || pre.length == 0 || in == null || in.length == 0) return null;
        TreeNode root = new TreeNode(pre[0]);
        int inIndex = 0;
        while (in[inIndex++] != pre[0]);
        inIndex -- ; //譬如inIndex = 3
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,inIndex +1),
                Arrays.copyOfRange(in,0,inIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,inIndex+1,pre.length),
                Arrays.copyOfRange(in,inIndex+1,in.length));
        return root;
    }
    public static void main(String[] args) {
        TreeUtil.printTree(reConstructBinaryTree(new int[]{1, 2, 4, 7, 3, 5, 6, 8}, new int[]{4, 7, 2,
                1, 5, 3,
                8, 6}));
    }
}
